package edu.cuit.avatar.parallel;

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * @author <a href="mailto:1020zhaodan@163.com">Adan</a>
 * @version 1.0
 * @date 2025/7/18 9:34
 */
public class ParallelMergeSort {
    public static void sort(int[] list){
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new SortTask(list));
    }

    /**
     * ForkJoinTask是用于任务的抽象基类
     *      RecursiveAction：定义不返回值的任务
     *      RecursiveTask：定义返回值的任务
     */
    private static class SortTask extends RecursiveAction{
        private static final int THRESHOLD = 500;
        private int[] list;

        public SortTask(int[] list){
            this.list = list;
        }
        @Override
        protected void compute() {
            //分而治之的基础情况
            if(list.length < THRESHOLD){
                Arrays.sort(list);
            } else {
                //将数组拆分为两半(第一部分)
                int[] firstHalf = new int[list.length / 2];
                System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
                //在第一部分递归调用归并排序

                //将数组拆分为两半(第二部分)
                int size = list.length - list.length / 2;
                int[] secondHalf = new int[size];
                System.arraycopy(list, list.length / 2, secondHalf, 0, size);

                //invokeAll(tasks)方法都隐式地调用fork()来执行任务，以及join()等待任务完成
                invokeAll(new SortTask(firstHalf), new SortTask(secondHalf));

                //合并
                MergeSort.merge(firstHalf, secondHalf, list);
            }
        }
    }
}
